package src;

import sun.reflect.generics.tree.Tree;

import javax.swing.tree.TreeNode;
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/**
 * @author hp
 * @Classname Solution
 * @Description TODO
 * @Date 2021/6/15 20:26
 */
public class Solution
{
    public static void main(String[] args)
    {

    }

    /**
     * 夏日炎炎，小男孩 Tony 想买一些雪糕消消暑。
     * <p>
     * 商店中新到 n 支雪糕，用长度为 n 的数组 costs 表示雪糕的定价，其中 costs[i] 表示第 i 支雪糕的现金价格。Tony 一共有 coins 现金可以用于消费，他想要买尽可能多的雪糕。
     * <p>
     * 给你价格数组 costs 和现金量 coins ，请你计算并返回 Tony 用 coins 现金能够买到的雪糕的 最大数量 。
     * <p>
     * 注意：Tony 可以按任意顺序购买雪糕。
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/maximum-ice-cream-bars
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param costs
     * @param coins
     * @return
     */
    public int maxIceCream(int[] costs, int coins)
    {
        int[] freq = new int[100001];
        for (int cost : costs)
        {
            freq[cost]++;
        }
        int count = 0;
        for (int i = 1; i <= 100000; i++)
        {
            if (coins >= i)
            {
                int curCount = Math.min(freq[i], coins / i);
                count += curCount;
                coins -= i * curCount;
            }
            else
            {
                break;
            }
        }
        return count;
    }

    static final Map<Integer, List<Integer>> map = new HashMap<>();

    ;

    /**
     * LCP 07. 传递信息
     * 小朋友 A 在和 ta 的小伙伴们玩传信息游戏，游戏规则如下：
     * <p>
     * 有 n 名玩家，所有玩家编号分别为 0 ～ n-1，其中小朋友 A 的编号为 0
     * 每个玩家都有固定的若干个可传信息的其他玩家（也可能没有）。传信息的关系是单向的（比如 A 可以向 B 传信息，但 B 不能向 A 传信息）。
     * 每轮信息必须需要传递给另一个人，且信息可重复经过同一个人
     * 给定总玩家数 n，以及按 [玩家编号,对应可传递玩家编号] 关系组成的二维数组 relation。返回信息从小 A (编号 0 ) 经过 k 轮传递到编号为 n-1 的小伙伴处的方案数；若不能到达，返回 0。
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/chuan-di-xin-xi
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param n
     * @param relation
     * @param k
     * @return
     */
    public int numWays(int n, int[][] relation, int k)
    {
        for (int[] ints : relation)
        {
            List<Integer> list = null;
            if (map.containsKey(ints[0]))
            {
                list = map.get(ints[0]);
            }
            else
            {
                list = new ArrayList<>();
            }
            list.add(ints[1]);
            map.put(ints[0], list);
        }

        System.out.println(map);
        int sum = findNext(map.get(0), 0, k, n);
        return sum;
    }

    private int findNext(List<Integer> list, int i, int i1, int n)
    {
        int sum = 0;

        if (i1 == 0)
        {
            if (i == n - 1)
            {
                return 1;
            }
            else
            {
                return 0;
            }

        }
        if (list != null)
        {
            for (Integer key : list)
            {
                sum += findNext(map.get(key), key, i1 - 1, n);
            }
        }

        return sum;
    }

    /**
     * 64. 最小路径和
     * <p>
     * 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
     * <p>
     * 说明：每次只能向下或者向右移动一步。
     *
     * @param grid
     * @return
     */
    public int minPathSum(int[][] grid)
    {
        int m = grid.length;
        int n = grid[0].length;
        int[][] temp = new int[m][n];
        temp[0][0] = grid[0][0];

        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (i == 0 && j == 0)
                {
                    continue;
                }
                if (i == 0 && j > 0)
                {
                    temp[i][j] = grid[i][j] + temp[i][j - 1];
                }
                else if (j == 0 && i > 0)
                {
                    temp[i][j] = grid[i][j] + temp[i - 1][j];
                }
                else
                {
                    temp[i][j] = grid[i][j] + Math.min(temp[i - 1][j], temp[i][j - 1]);
                }

            }
        }
        return temp[m - 1][n - 1];

    }

    /**
     * 给定一个化学式formula（作为字符串），返回每种原子的数量。
     * <p>
     * 原子总是以一个大写字母开始，接着跟随0个或任意个小写字母，表示原子的名字。
     * <p>
     * 如果数量大于 1，原子后会跟着数字表示原子的数量。如果数量等于 1 则不会跟数字。例如，H2O 和 H2O2 是可行的，但 H1O2 这个表达是不可行的。
     * <p>
     * 两个化学式连在一起是新的化学式。例如 H2O2He3Mg4 也是化学式。
     * <p>
     * 一个括号中的化学式和数字（可选择性添加）也是化学式。例如 (H2O2) 和 (H2O2)3 是化学式。
     * <p>
     * 给定一个化学式 formula ，返回所有原子的数量。格式为：第一个（按字典序）原子的名字，跟着它的数量（如果数量大于 1），然后是第二个原子的名字（按字典序），跟着它的数量（如果数量大于 1），以此类推。
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/number-of-atoms
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */
    public String countOfAtoms(String formula)
    {
        return formula;
    }

    public int maxProfit(int[] prices)
    {
        int ans = 0;
        int max = prices[0], min = prices[0];
        for (int i = 1; i < prices.length; i++)
        {
            if (min > prices[i] || max >= prices[i])
            {
                ans += max - min;
                min = prices[i];

            }
            max = prices[i];
        }
        ans += max - min;

        return ans;
    }

    public int maxProfit2(int[] prices)
    {
        int ans = 0;
        int max = prices[0], min = prices[0];
        for (int i = 1; i < prices.length; i++)
        {
            if (min > prices[i])
            {
                ans = Math.max(ans, max - min);
                min = prices[i];
                max = prices[i];
            }
            else
            {
                if (max < prices[i])
                {
                    max = prices[i];
                }
            }
        }
        ans = Math.max(ans, max - min);

        return ans;
    }

    public int[] intersect(int[] nums1, int[] nums2)
    {
        int[] ans = new int[nums1.length+nums2.length];
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int i = 0, j = 0;
        int index =0;
        while (i < nums1.length && j < nums2.length)
        {
            if (nums1[i] == nums2[j])
            {
                ans[index++]=nums1[i];
                i++;
                j++;
            }
            else if (nums1[i] > nums2[j])
            {
                j++;
            }
            else
            {
                i++;
            }
        }
        return Arrays.copyOfRange(ans,0,index-1);
    }
}
